package algorithmTopics.string;


import java.util.*;
import java.util.stream.Collectors;

/**
 * 用于练习 leet code 里面关于字符串的题目
 *
 * @author 86155
 * @date 2025/05/14
 */
public class Solution {
    /**
     * num distinct
     * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
     *
     * @param s s
     * @param t t
     * @return int
     */
    public int numDistinct(String s, String t) {
        char[] chars = s.toCharArray();
        char[] target = t.toCharArray();
        return numDistinct(chars, 0, target, 0);
    }

    private int numDistinct(char[] chars, int s, char[] target, int t) {

        if (chars.length - s < target.length - t) {
            return 0;
        }
        if (t >= target.length) {
            return 1;
        }
        int res = numDistinct(chars, s + 1, target, t);
        if (chars[s] == target[t]) {
            res += numDistinct(chars,s+1,target,t+1);
        }
        return res;

    }


    /**
     * 最小删除总和
     * 给定两个字符串s1 和 s2，
     *
     * @param s1 s1
     * @param s2 s2
     * @return int 返回 使两个字符串相等所需删除字符的 ASCII 值的最小和
     */
    public int minimumDeleteSum(String s1, String s2) {
        //统计字符数量
        char[] char1 = s1.toCharArray();
        char[] char2 = s2.toCharArray();
        int m = s1.length();
        int n = s2.length();
        //动态数组 标识当前长度的字符的使两个字符串相等所需删除字符的 ASCII 值的最小和
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        int temp = 0;
        for (int i = 0; i < n; i++) {
            temp += char2[i];
            dp[0][i + 1] = temp;
        }
        temp = 0;
        for (int i = 0; i < m; i++) {
            temp += char1[i];
            dp[i + 1][0] = temp;
            for (int j = 0; j < n; j++) {
                // 相等就选取上一步的匹配最小值
                //不相等 就两个都一起删除，或者删除其中一个
                dp[i + 1][j + 1] = char1[i] == char2[j] ?
                        Math.min(dp[i][j], Math.min(dp[i][j + 1] + char1[i], dp[i + 1][j] + char2[j])) :
                        Math.min(dp[i][j] + char1[i] + char2[j], Math.min(dp[i][j + 1] + char1[i], dp[i + 1][j] + char2[j]));
            }
        }
        return dp[m][n];
    }

    /**
     * 最小距离
     *
     * @param word1 word1
     * @param word2 word2
     * @return int
     */
    public int minDistance(String word1, String word2) {
        //迭代
        char[] s = word1.toCharArray();
        char[] t = word2.toCharArray();
        int n = s.length;
        int m = t.length;
        //动态数组
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < m; i++) {
            dp[0][i + 1] = i + 1;
        }
        // 从左往右计算，依次遍历即可
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = i + 1;
            for (int j = 0; j < m; j++) {
                dp[i + 1][j + 1] = s[i] == t[j] ?
                        dp[i][j] : Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
            }
        }
        return dp[n][m];
    }

    /**
     * ，找出其中最长的回文子序列，
     *
     * @param s s
     * @return int 并返回该序列的长度。
     */
    public int longestPalindromeSubseq(String s) {
        char[] array = s.toCharArray();
        int len = s.length();
        //递归动态数组
        int[][] memo = new int[len][len];
        for (int[] arr : memo) {
            Arrays.fill(arr, -1);
        }
        return longestPalindromeSubseqHandler(0, len - 1, array, memo);
    }

    private int longestPalindromeSubseqHandler(int left, int right, char[] array, int[][] memo) {

        if (left > right) {
            //没有字符串了
            return 0;
        } else if (left == right) {
            //只有一个字符
            return 1;
        }
        if (memo[left][right] != -1) {
            //记忆过
            return memo[left][right];
        }
        if (array[left] == array[right]) {
            //说明可以同时推进
            return memo[left][right] = longestPalindromeSubseqHandler(left + 1, right - 1, array, memo) + 2;
        }
        return memo[left][right] = Math.max(longestPalindromeSubseqHandler(left + 1, right, array, memo),
                longestPalindromeSubseqHandler(left, right - 1, array, memo));
    }

    /**
     * 分词
     *
     * @param s        s
     * @param wordDict 单词字典
     * @return boolean
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        wordDict.sort((a, b) -> b.length() - a.length());
        int maxLen = wordDict.get(0).length();
        HashSet<String> set = new HashSet<>(wordDict);
        int n = s.length();
        // // 创建动态规划数组f，f[i]表示字符串s的前i个字符（s[0:i)）是否可以被分割
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // 遍历每一个 s 中的词
        for (int i = 1; i <= n; i++) {
            //maxLen 就是最长的，大于这个没有必要进行分割
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
                // 如果f[j]为true（表示前j个字符可分割），且子串s[j:i]在字典中
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    /**
     * 字符串相乘
     *
     * @param num1 num1
     * @param num2 num2
     * @return {@link String}
     */
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        //装载结果
        int[] res = new int[num1.length() + num2.length()];
        //遍历两个字符串的每一位，用俩个数字相乘，优化了竖式相乘的中间部分 ，所在的位置就是他们需要加的位置
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = (res[i + j + 1] + n1 * n2);
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) {
                continue;
            }
            result.append(res[i]);
        }
        return result.toString();

    }

    /**
     * 二进制返回
     * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     *
     * @param a a
     * @param b b
     * @return {@link String}
     */
    public String addBinary(String a, String b) {
        //转载结果集合
        StringBuilder res = new StringBuilder();
        //从小到大遍历 手动计算二进制
        int i = a.length() - 1;
        int j = b.length() - 1;
        boolean isEnter = false;
        while (i >= 0 || j >= 0 || isEnter) {
            //有任何一个都需要计算 每一位都是0-9
            int num1 = i >= 0 ? a.charAt(i) - '0' : 0;
            int num2 = j >= 0 ? b.charAt(j) - '0' : 0;
            int total = isEnter ? num1 + num2 + 1 : num1 + num2;
            //判断是否进位
            isEnter = total >= 2;
            if (isEnter) {
                //进位
                res.append(total - 2);
            } else {
                res.append(total);
            }
            i--;
            j--;
        }

        //从大到小
        return res.reverse().toString();
    }

    /**
     * 机器人是有界
     *
     * @param instructions 说明
     * @return boolean
     */
    public boolean isRobotBounded(String instructions) {
        //方法一：暴力就是循环四次 看看最终的坐标在哪里
        //四个方向变量存储步数 上下左右
        int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //最初方向是 0
        int direction = 0;
        // 方法二：也可以找寻规律，循环一次后不进入循环的条件是，坐标改变 且 方向向上
        int x = 0, y = 0;
        for (char a : instructions.toCharArray()) {
            if (a == 'G') {
                x += dir[direction][0];
                y += dir[direction][1];
            } else if (a == 'R') {
                if (direction + 1 > 3) {
                    direction = 0;
                } else {
                    direction++;
                }
            } else if (a == 'L') {
                if (direction - 1 < 0) {
                    direction = 3;
                } else {
                    direction--;
                }
            }
        }

        return x == 0 && y == 0 || direction != 0;
    }

    /**
     * 是否能够回到原点
     *
     * @param moves 移动
     * @return boolean
     */
    public boolean judgeCircle(String moves) {
        int u = 0;
        int r = 0;
        // 对称的次数
        for (char i : moves.toCharArray()) {
            if (i == 'U') {
                u++;
            } else if (i == 'D') {
                u--;
            } else if (i == 'R') {
                r++;
            } else {
                r--;
            }
        }
        return r == 0 && u == 0;
    }

    /**
     * 转小写
     *
     * @param s s
     * @return {@link String}
     */
    public String toLowerCase(String s) {
        int len = s.length();
        StringBuilder builder = new StringBuilder(len);
        for (int i = 0; i < len; i++) {
            char a = s.charAt(i);
            if (a >= 65 && a <= 90) {
                a |= 32;
            }
            builder.append(a);
        }
        return builder.toString();
    }

    /**
     * 最后一个单词长度
     *
     * @param s s
     * @return int
     */
    public int lengthOfLastWord(String s) {
        return Arrays.stream(s.split(" ")).reduce((a, b) -> a = b).get().length();
    }

    /**
     * 从罗马转整数
     *
     * @param s s
     * @return int
     */
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int res = 0;
        int len = s.length();
        //小的数字在大的数字的右边
        //倒着遍历
        for (int i = len - 1; i >= 0; i--) {
            int curr = map.get(s.charAt(i));
            int next = 0;
            if (i - 1 >= 0) {
                next = map.get(s.charAt(i - 1));
            }
            if (curr <= next) {
                res += curr;
            } else {
                res = res + curr - next;
                i--;
            }
        }

        return res;
    }

    /**
     * 重复子串模式
     * 检查是否可以通过由它的一个子串重复多次构成。
     *
     * @param s s
     * @return boolean
     */
    public boolean repeatedSubstringPattern(String s) {
        // 求最长公共前后缀
        int len = s.length();
        // 公共前后缀
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];
        for (int i = 2, j = 0; i < len + 1; i++) {
            while (j > 0 && chars[i] != chars[j + 1]) {
                // 匹配不成功
                j = next[j];
            }
            if (chars[i] == chars[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        int i = next[len];

        return i % (len - i) == 0 && i >= (len + 1) / 2;
    }

    /**
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
     *
     * @param s s
     * @param t t
     * @return boolean
     */
    public boolean isAnagram(String s, String t) {
        // 统计每个字符出现的次数
        int len1 = s.length();
        int len2 = t.length();
        if (len1 != len2) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < len1; i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int i : count) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param haystack 干草堆
     * @param needle   针头
     * @return int 你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）
     */
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        //添加空格使其从下标1开始
        haystack = " " + haystack;
        needle = " " + needle;
        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();
        //构建next 数组 ，使用KMP算法 ,也就是寻找最长公共前后缀
        int[] next = new int[m + 1];
        for (int i = 2, j = 0; i < m + 1; i++) {
            //匹配不成功
            // j 向前移动
            while (j > 0 && p[i] != p[j + 1]) {
                j = next[j];
            }
            //匹配成功
            if (p[i] == p[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        for (int i = 1, j = 0; i <= n; i++) {
            while (j > 0 && s[i] != p[j + 1]) {
                j = next[j];
            }
            if (s[i] == p[j + 1]) {
                j++;
            }
            if (j == m) {
                return i - m;
            }
        }

        return -1;
    }

    /**
     * 找到差异
     *
     * @param s s
     * @param t t 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母
     * @return char 请找出在 t 中被添加的字母
     */
    public char findTheDifference(String s, String t) {
        if (s.equalsIgnoreCase("")) {
            return t.charAt(0);
        }
        int[] nums = new int[26];
        for (char a : s.toCharArray()) {
            nums[a - 'a']++;
        }
        char res = 'a';
        for (char b : t.toCharArray()) {
            if (nums[b - 'a'] == 0) {
                res = b;
                break;
            }
            nums[b - 'a']--;
        }

        // 方法二return (char) (s + t).chars().reduce( (a ,b) -> a^=b).getAsInt();

        return res;
    }

    /**
     * 交替合并
     *
     * @param word1 word1
     * @param word2 word2
     * @return 合并后的字符串
     */
    public String mergeAlternately(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        StringBuilder builder = new StringBuilder(len1 + len2);
        //交叉合并
        int i = 0, j = 0;
        for (int k = 0; i < len1 && j < len2; k++) {
            if (k % 2 == 0) {
                builder.append(word1.charAt(i++));
            } else {
                builder.append(word2.charAt(j++));
            }
        }
        if (len1 > len2) {
            builder.append(word1.toCharArray(), i, len1 - i);
        } else {
            builder.append(word2.toCharArray(), j, len2 - j);
        }
        return builder.toString();
    }

    /**
     * 解码字符串
     *
     * @param s s
     * @return 按规则解析后的字符串
     */
    public String decodeString(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<String> strings = new Stack<>();
        // 得到的字符串
        String curr = "";
        //对应的数字
        int count = 0;
        for (char a : s.toCharArray()) {
            if (a == '[') {
                //存放当前 数字和字符串
                nums.push(count);
                strings.push(curr);
                // 还原
                curr = "";
                count = 0;
            } else if (a == ']') {
                // 需要进行结算
                StringBuilder builder = new StringBuilder(strings.pop());
                int loop = nums.pop();
                for (int i = 0; i < loop; i++) {
                    builder.append(curr);
                }
                curr = builder.toString();
            } else if (Character.isDigit(a)) {
                //数字就拼接
                count = count * 10 + a - '0';
            } else {
                //字母拼接
                curr += a;
            }

        }

        return curr;
    }

    /**
     * 最长回文字串
     *
     * @param s s
     * @return 回文字串
     */
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        // 中心扩散算法
        for (int i = 0; i < s.length(); i++) {
            // 一个数扩散，两数直接扩散
            int len = Math.max(longestPalindromeHelper(s, i, i),
                    longestPalindromeHelper(s, i, i + 1));
            if (len > end - start) {
                // 说明当前的长度大
                end = i + len / 2;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int longestPalindromeHelper(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    /**
     * 是有效 的括号组合
     *
     * @param s s
     * @return boolean
     */
    public boolean isValid(String s) {
        // 用栈来存储
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(')');
            } else if (s.charAt(i) == '[') {
                stack.push(']');
            } else if (s.charAt(i) == '{') {
                stack.push('}');
            } else {
                // 出栈
                if (stack.isEmpty() || s.charAt(i) != stack.pop()) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> tCount = new HashMap<>();
        int less = 0;
        // count letters in t
        for (int i = 0; i < t.length(); i++) {
            if (tCount.get(t.charAt(i)) == null) {
                less++;
            }
            tCount.merge(t.charAt(i), 1, Integer::sum);
        }
        // 初始化左右边界
        int m = s.length();
        int ansL = -1;
        int ansR = m;


        //limit the subString length
        for (int left = 0, right = 0; right < m; right++) {
            char c = s.charAt(right);
            // 右端点移入子串
            tCount.merge(c, -1, Integer::sum);
            if (tCount.get(c) == 0) {
                less--;
            }
            //涵盖了t
            while (less == 0) {
                // find shorter substring
                if (right - left < ansR - ansL) {
                    ansL = left;
                    ansR = right;
                }
                //移除左端点
                char x = s.charAt(left);
                if (tCount.get(x) == 0) {
                    less++;
                }
                tCount.merge(x, 1, Integer::sum);
                left++;
            }

        }
        return ansL < 0 ? "" : s.substring(ansL, ansR + 1);

    }

    /**
     * min窗口 子串
     *
     * @param
     * @param t t
     * @return {@link String}
     */
   /* public String minWindow(String s, String t) {
        HashMap<Character, Integer> tCount = new HashMap<>();
        HashMap<Character, Integer> sCount = new HashMap<>();
        // count letters in t
        for(int i = 0 ; i < t.length(); i++){
            tCount.merge(t.charAt(i),1,Integer::sum);
        }
        // 初始化左右边界
        int m = s.length();
        int ansL = -1;
        int ansR = m;


        //limit the subString length
        for (int left = 0,right = 0; right < m; right++) {
            // add letters
            sCount.merge(s.charAt(right),1,Integer::sum);
            //涵盖了t
            while (isCovered(tCount, sCount, t)) {
                // find shorter substring
                if (right - left < ansR - ansL) {
                    ansL = left;
                    ansR = right;
                }
                //移除左端点
                sCount.merge(s.charAt(left),-1,Integer::sum);
                left++;
            }

        }
        return ansL < 0 ? "" : s.substring(ansL,ansR+1);

    }*/
    //是否覆盖 ensure t all letters in s
    private boolean isCovered(HashMap<Character, Integer> tCount, HashMap<Character, Integer> sCount, String t) {
        //ensure t all letters in s
        for (int i = 0; i < t.length(); i++) {
            if (tCount.get(t.charAt(i)) - 0 > sCount.getOrDefault(t.charAt(i), 0)) {
                return false;
            }
        }
        return true;
    }

    //方法二排序
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> collect = Arrays.stream(strs).collect(Collectors.groupingBy(str -> {
            // 返回排序后的字符串
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }));
        return new ArrayList<>(collect.values());
    }

    // 方法一 破解
//    public List<List<String>> groupAnagrams(String[] strs) {
//        List<List<String>> res = new ArrayList<>();
//        // 来存储 不同字符的 单词个数
//        List<Map<Character,Integer>> mapList = new ArrayList<>();
//
//        // 一个一个判断 ，并加入 res
//        for (int i = 0; i < strs.length; i++) {
//            String s = strs[i];
//            boolean isAdd = false;
//            // 进行字符串解析
//            Map<Character, Integer> nowWords = wordsInString(s);
//            if (mapList.size() != 0) {
//                //和已经有的单词组 构成进行比较
//                for (int j = 0; j < res.size(); j++) {
//                    if (mapIsSame(mapList.get(j), nowWords, s)) {
//                        //找到相同构成,放入同一组
//                        List<String> strings = res.get(j);
//                        strings.add(s);
//                        isAdd = true;
//                        break;
//                    }
//                }
//
//            }
//            if (!isAdd) {
//
//                // 新的一组 添加进来
//                mapList.add(nowWords);
//                List<String> piece = new ArrayList<>();
//                piece.add(s);
//                res.add(piece);
//
//            }
//        }
//
//        return res;
//    }

    /**
     * 判断是否为同一组别，相同的单词构成
     *
     * @param map1 map1
     * @param map2 map2
     * @return boolean
     */
    private boolean mapIsSame(Map<Character, Integer> map1, Map<Character, Integer> map2, String s) {
        if (map1.size() != map2.size()) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            if (map1.get(s.charAt(i)) == null || map2.get(s.charAt(i)) == null) {
                return false;
            }
            if (!map1.get(s.charAt(i)).equals(map2.get(s.charAt(i)))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 字符串中单词解析
     *
     * @param s s
     * @return {@link Map}<{@link Character}, {@link Integer}>
     */
    private Map<Character, Integer> wordsInString(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == null) {
                map.put(s.charAt(i), 1);
            } else {
                Integer integer = map.get(s.charAt(i));
                map.put(s.charAt(i), integer + 1);
            }
        }
        return map;
    }

    public int minMaxDifference(int num) {
        String s = String.valueOf(num);
        int big = 0;
        char bigTemp = 'A';
        char smallTemp = 'A';
        int small = 0;
        for (int i = 0; i < s.length(); i++) {
            //把变大的数字拼出来
            char now = s.charAt(i);

            if (bigTemp == 'A' && now != '9') {
                bigTemp = now;
            }
            //判断是不是需要 替换的那个数字
            if (bigTemp == now) {
                big = big * 10 + 9;
            } else {
                big = big * 10 + (now - '0');
            }

            if (smallTemp == 'A' && now != '0') {
                smallTemp = now;
            }
            //判断是不是需要 替换的那个数字
            if (smallTemp == now) {
                small = small * 10;
            } else {
                small = small * 10 + (now - '0');
            }

        }

        return big - small;
    }


    /*给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
    示例 1:
    输入: s = "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。*/

    // 方法一 太慢了 存储字符串
    // 方法二 思路是一样的，直接下标来计算，重复下标之前的都舍去

    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        //存储最大的不重复字符
        int res = 1;
        // 当前的不重复字符
        String now = s.charAt(0) + "";
        for (int i = 0; i < s.length() - 1; i++) {
            //下一个字符是不是 在最大字符串中
            int index = now.indexOf(s.charAt(i + 1));
            //加长当前的字符串
            now += s.charAt(i + 1);
            if (index != -1) {
                //如果相等，得看当前字符 与当前字符中的哪一个重复了 截断之前的字符
                now = now.substring(index + 1);
            }
            res = res > now.length() ? res : now.length();
        }
        return res;
    }

}
